The present invention relates to the field of Content Addressable Memory (CAM). More particularly, the invention relates to a method and apparatus for storing associative ranges containing keys and data associated with said ranges, in form of a lookup table, in which a searched associative key found within a range is used to extract the associated data.
Content Addressable Memory (CAM) devices are specially designed for storing information in the form of a lookup table. CAM structures allow a direct and fast search of data items, a search which is based on an associative key. Software implementations of such data structures are usually slow for real time applications, especially in view of the great advances of the recent years, in data transmission rates.
In general, CAM comprises storage of key words, and a separate storage for associated data items. For each of the stored key words, there is a corresponding associated data item. Therefore, the structure and operation of CAMs differs from those of conventional memory devices, such as RAM, wherein each data item is addressed by utilizing a unique address. In CAMs, data items are fetched from the CAM device by submitting a key value. The key words storage is then searched to determine if a matching key word is stored inside the CAM. If there is a key-matching entry found in the CAM, a xe2x80x98matchxe2x80x99 indication is issued, and the corresponding associated data (i.e., the data item associated with the key) is output from the CAM. If there is no matching key, a xe2x80x98mismatchxe2x80x99 indication is issued.
The efficiency and high speed, inherent to the CAM implementations, makes them very attractive for address filtering and routing in networking applications. The Internet routers, for instance, maintain a list of Internet Protocol (IP) Destination Addresses (IPDAs), and their associated interfaces (e.g., port numbers) through which the router should forward the received packet. This list is utilized to determine the best route for a packet of information received by the router to reach its destination. More particularly, said list of IPDAs and the interfaces is organized in the form of a lookup table. The key word associated with each IPDA, is the router interface of the destined network node (i.e., the next routing point, to which the received packet is destined).
Each IPDA is a unique 32-bit entity, usually represented in the form of four octets (sequences of eight bits, e.g., 192.30.50.0), comprising address information of the destined node within that network.
The original IP network classification method, utilizing five basic Classes for any network on the Internet, turned out to be very expansive in terms of IPDA address space consumption, and in terms of the routing table size, required for forwarding lookups. As a consequence, the Internet ran out of address space very quickly. This has also led to an outstanding growth in the size of the routers"" lookup tables.
I order to overcome the problems described herein above, the Internet Engineering Task Force (IETF) devised a more flexible method (as described in RFC1519), known as the Classless Inter-Domain Routing (CIDR). The CIDR resolves the difficulties stemming from the original network Address-Class hierarchy by aggregating multiple routes into a single representation. Address aggregation is achieved by masking a contiguous number of address 32-p least significant bits, which leads to a representation of a range of addresses by a single address and its mask. This leaves p bits also defined as the address prefix, which should be compared. p can be any integer value from 0 to 32. The convention used to describe a CIDR address entry is A/p, where A is the address and p is the prefix. For example, the CIDR address entry 192.30.50.0/24 matches any IPDA address in the range 192.30.50.0←xe2x86x92192.30.50.255.
Generally a CIDR address may match with multiple number of entries in the router""s key list, this due to the presence of overlapping address ranges. Selection of one out of multiple matches is based upon the most specific match, which is the one with the longest prefix.
The CIDR addressing scheme allows a more efficient allocation of IP addresses, which results in significant reduction in the size of the routing table, yet the growth of the Internet is seems to be increasing with time, and the difficulties stemming from this growth in routing table size still remain.
The modern routers are now designed for CIDR compliance. Ternary CAM technology is widely adopted in routers implementation, but the substantial growth in the size of routing tables, and the many comparison operations required to determining a key match, influence performance and power consumption. Other complications in Ternary CAM (TCAM) implementations are due to the complexity involved in determining the key match to a range of possible values, and especially utilizing CIDR""s longest-prefix-match policy. The conventional CAM implementations are efficiently designed for lookup tables when an exact match of key values is required, but the situation is more complex when a range of values need to be matched. Moreover, the aggregation efficiency is greatly influenced by the allocated address space, which in many cases is not covered by a single mask prefix, resulting in a substantial increase of routing table""s sizes.
In addition, Ternary CAMs are limited with respect to the ranges boundaries, which are limited only to integer values being xcex1xc2x7232xe2x88x92p, where a is an integer, and p is the prefix length. Therefore, the boundary values do not represent the whole range of non-negative integer values. This eliminates the capability of further aggregation over and beyond the one offered by the CIDR method.
Since, multiple matches are feasible all the entries must be simultaneously compared to a key, which stems in a high power consumption, that grows proportionally to the number of entries and with the lookup rate. For instance a typical 64 K Ternary CAM consumes about 10 Watts at a rate of 66 million lookups per second.
Due to the requirement to arrange Ternary CAM entries in prefix-length order, the database update may become cumbersome and lengthy in time.
Ternary CAM""s basic cell is complex, since it incorporates the address, the mask and the comparator. The resulting cell size, substantially limits the amount of entries per TCAM device in comparison with an SRAM. The biggest TCAM (for instance SiberCore""s SiberCAM Ultra-2M) implemented today, incorporates 64 K IPv4 CIDR address entries without the associated data.
xe2x80x9cIP Lookups using Multiway and Multicolumn Searchxe2x80x9d, B. Lampson et al, Proceedings of IEEE Infocom, Volume 3, April 1998, pages 1248-1256 discloses a search method based on an interaction between a processing device and a memory, using binary search based algorithm for CIDR address searches. This method results in having a unique memory entry in which the result may reside. However, it offers a search performance, which varies as log2 n, where n represents the number of entries. This is worse in performance than a Ternary CAM, which is insensitive to the lookup table size. Furthermore, this implementation is unsuitable for high-performance routing, due to it lookup rate limitation.
All the methods described above have not yet provided satisfactory solutions to the problem of efficient storage of associative data in lookup tables, and which might result in low power consumption and in high search performance.
It is an object of the present invention to provide a Range Content Addressable Memory (RCAM) being capable of Searching a whether a submitted key belongs to a range bounded by two non-negative integers, that has a common associated data.
It is another object of the present invention to provide an RCAM for storing and searching associative data items related to, disjoined and/or overlapping ranges.
It is another object of the present invention to provide an RCAM, which allows efficient associative data aggregation, using less storage space.
It is a further object of the present invention to provide an RCAM, in which the power consumption does not grow in proportion with the amount of data entries stored and searched.
It is a still another object of the present invention to provide an RCAM, in which the associating keys are represented in an efficient form.
Other objects and advantages of the invention will become apparent as the description proceeds.
The present invention is directed to a method for arranging and storing, in a memory, associative key data set of associative elements and a corresponding associated data set of associated elements, where each associative element corresponds to a range of consecutive values, such that an associated element may be extracted from the memory as valid data if an associative key belongs to its associative element, the range may be represented by its lower and upper extreme values. A memory device(s) is provided for storing the associative key data set and the associated data set, that comprises a first and a second storage areas, so that to each storage location in the first storage area there is a corresponding storage location in the second storage area. The associative elements of the key association data set and their corresponding associated data set are arranged in an order determined by priority precedence, such that associative elements having higher priority are placed before associative elements having lower priority A unique index is assigned for each associative element for representing its ordered location. At least one of the extreme values of each associative element is stored in the first storage area in a location that corresponds to the priority of the associative element. Each value of the associated data set is stored in a location in the second storage area, that corresponds to the location of the associative element to which it is associated.
Preferably, associated data values are extracted from the memory upon conducting a key search on the associative key data. Upon receiving an input key, one or more associative elements that may contain the input key are sought, and if no such associative element(s) is found, a mismatch signal is output, for indicating that the associated data that is output is invalid. If the input key is contained in one or more associative element(s), the associated data that corresponds to the associative element having the highest priority that contains the input key, and a match signal indicating that the associated data that is being output is valid, are output.
3. The lower and/or the upper extreme value of one or more ranges may be a non-negative value. The associative elements of the key association data set may be ranges of consecutive values having semi-open/semi-closed boundaries. Each range may have a closed boundary as its lower boundary, and an opened boundary as its upper boundary, thereby defining a range of associative elements, each of which contains the value of its corresponding lower boundary and all its consecutive values, except for the value of its upper boundary. Alternatively, each range may have a closed boundary as its upper boundary, and an opened boundary as its lower boundary, thereby defining a range of associative elements, each of which contains the value of its corresponding upper boundary and all its consecutive values, except for the value of its lower boundary. The ranges that correspond to different associative elements may be non-overlapping ranges.
Preferably, whenever the ranges that corresponds to different associative elements are overlapping ranges, the overlapping ranges are converted into one or more equivalent non-overlapping ranges. Overlapping ranges are combined by truncating overlapping portions from ranges having lower priority, while maintaining with no change, for each set of overlapping portions, a single portion having the highest priority within the set, thereby obtaining an equivalent set of non-overlapping ranges. The non-overlapping ranges of the equivalent set are arranging in a descending/ascending order, according to the boundary values of each of the ranges.
Preferably, whenever a first range contains both, the upper and the lower, boundaries of a second range with lower priority, the second range is represented by the first range. The second range element is removed from the associated key data set, and its associated data element is removed from the associated data set. Whenever a first range contains only the upper boundary of a second range with lower priority, the second range is truncated to include the interval of values between its lower boundary and the lower boundary of the second range, thereby obtaining adjacent ranges having the same data association that corresponds to the first and the second ranges. Whenever a first range contains only the lower boundary of a second range with lower priority the second range is truncated to include the interval of values between its upper boundary and the upper boundary of the first range, thereby obtaining adjacent ranges having the same data association that corresponds to the first and the second ranges. Whenever both, the upper and the lower, boundaries of a first range are contained in a second range with lower priority the second range is truncated into two smaller ranges, a first smaller range that includes the interval between the lower boundary of the second range and the lower boundary of the first range, and a second smaller range that includes the interval between the upper boundary of the first range and the upper boundary of the second range, thereby obtaining three adjacent ranges where the two smaller ranges have data association which is the same as the data association of the second range, while the first range and its data association remain unchanged. This process is repeated for pairs of overlapping ranges as long as there is an overlap between more than two ranges, each time for the resulting ranges, until the last resulting ranges do not overlap.
Preferably, associated data values are extracted from the memory upon conducting a key search on the associative key data. Upon receiving an input key, one or more associative equivalent non-overlapping ranges that may contain the input key are sought, and if no such associative equivalent non-overlapping range(s) is found, a mismatch signal is output for indicating that the associated data that is being output is invalid. If the input key is contained in an associative equivalent non-overlapping range, the associated data that corresponds to that associative equivalent non-overlapping range is output, and a match signal indicating that the associated data that is being output is valid.
Preferably, match between an input key and an associative element is detected using a single comparison between the input key and the boundaries of equivalent non-overlapping ranges. The key association data set is converted into an equivalent non-overlapping data set. The boundary values of the equivalent non-overlapping data set are stored in an ascending order in the first storage area. Boundary type information is stored in a third storage area. The boundary type information indicates if a boundary is opened or closed, thereby having for each location in the first storage area a corresponding location in the third storage area. The associated data set is stored in the second storage area in locations that correspond to the locations of closed boundaries of the equivalent non-overlapping data set stored in the first storage area. A key match is detected by concurrently performing a single comparison operation between each boundary value stored in the first storage area and the input key, to determine whether the input key is larger than the boundary value. A TRUE value is issued whenever a comparison result with the input key indicates that the input key is larger than the boundary value, otherwise, a FALSE value is issued. A match is detected whenever a transition of the comparison results, from a TRUE value to a FALSE value is obtained. The index of the match being the index of the last boundary value for which a TRUE value has been obtained, is issued. The boundary type information is retrieved from the third storage area that corresponds to the index, so that a match is obtained whenever the retrieved boundary type information indicates that the value with which the comparison operation was performed is a closed boundary value. The index is used to fetch the associated data from the second storage area.
Whenever each associative element comprises two values, a first value which is the lower boundary of a range, and a second value which is an upper boundary of the range, a key match is detected by concurrently performing two comparison operations for every range in the key association data set, a first comparison to determine whether the input key is larger than, or equals to, the range""s lower boundary, and a second comparison to determine whether the input key is smaller than the range""s upper boundary. A TRUE value is issued whenever the input key is larger than, or equals to, the range""s lower boundary, and smaller than the range""s upper boundary. A match is indicated to each range, which yields a TRUE value, and the match with the highest priority is selected. The index of the match having the highest priority is issued and the associated data is retrieved by utilizing this index. A validation signal, which is utilized to validate a match indication may be added to ignore search results in a desired location(s).
Whenever a value that belongs to a space that consists of one or more ranges, may be represented by k bits that represent the opened boundary of the space by k+1 bits, such that a xe2x80x9c0xe2x80x9d logic value is assigned to k consecutive bits and a xe2x80x9c1xe2x80x9d logic value is assigned to the remaining bit. Each value that does not belong to a range and is beyond the opened boundary of the range may be represented by k+1 bits, such that a xe2x80x9c0xe2x80x9d logic value is assigned to k consecutive bits and a xe2x80x9c1xe2x80x9d logic value is assigned to the remaining bit. The range may represent Classless Inter Domain Routing (CIDR) addresses.
Preferably, an input key search may be performed simultaneously in one or more associative elements, or in one or more equivalent non-overlapping ranges, that may contain the input key.
Whenever the ranges that corresponds to different associative elements are overlapping ranges, a match between an input key and a range is sought by arranging the ranges in their priority precedence order, comparing the input key with the values within each range, and obtaining one or more match indications whenever the input key belongs to one or more a ranges. The match indication corresponding to the range having the highest priority is selected.
The present invention is also directed to an apparatus for arranging and storing, in a memory, associative key data set of associative elements and a corresponding associated data set of associated elements, where each associative element corresponds to a range of consecutive values, such that an associated element may be extracted from the memory as valid data if an associative key belongs to its associative element, the range may be represented by its lower and upper extreme values. The apparatus comprises a memory device(s), for storing the associative key data set and the associated data set, that comprises a first and a second storage areas, so that to each storage location in the first storage area there is a corresponding storage location in the second storage area, in which the associative elements of the key association data set and their corresponding associated data set are arranged in an order determined by priority precedence, such that associative elements having higher priority are placed before associative elements having lower priority; a unique index is assigned for each associative element, representing its ordered location; at least one of the extreme values of each associative element is stored in the first storage area in a location that corresponds to the priority of the associative element; and each value of the associated data set is stored in a location in the second storage area, that corresponds to the location of the associative element to which it is associated.
The apparatus may further comprise circuitry for extracting associated data values from the memory upon conducting a key search on the associative key data, including:
a) circuitry for seeking one or more associative elements that may contain a searched input key, upon receiving the input key;
b) circuitry for outputting the associated data that corresponds to the associative element having the highest priority that contains the input key; and
c) circuitry for outputting a mismatch signal, indicating that the associated data that is being output is invalid, if no such associative element(s) is found and a match signal indicating that the associated data that is being output is valid, if the input key is contained in one or more associative element(s).
10. The lower and/or the upper extreme value of one or more ranges that are stored in the apparatus may be a non-negative value. The associative elements of the key association data set may be ranges of consecutive values having semi-open/semi-closed boundaries. Each range that is stored in the apparatus may have a closed boundary as its lower boundary, and an opened boundary as its upper boundary, or alternatively, a closed boundary as its upper boundary, and an opened boundary as its lower boundary. The ranges that correspond to different associative elements and stored in the apparatus may be non-overlapping ranges.
Overlapping ranges that are stored in the apparatus may be converted into one or more equivalent non-overlapping ranges, by combining overlapping ranges by truncating overlapping portions from ranges having lower priority, while maintaining with no change, for each set of overlapping portions, a single portion having the highest priority within the set and by arranging the non-overlapping ranges of the equivalent set in a descending/ascending order, according to the boundary values of each of the ranges.
The present invention is also directed to an apparatus in which associated data values may be extracted from the memory of the apparatus upon conducting a key search on the associative key data. This apparatus may comprise:
a) circuitry for seeking one or more associative equivalent non-overlapping ranges that may contain a searched input key, upon receiving the input key;
b) circuitry for outputting the associated data that corresponds to the associative equivalent non-overlapping range that contains the input key; and
c) circuitry for outputting a mismatch signal, indicating that the associated data that is being output is invalid, if no associative equivalent non-overlapping range is found and a match signal indicating that the associated data that is being output is valid, if the input key is contained in the associative equivalent non-overlapping range.
The present invention is also directed to an apparatus, in which a match between an input key and an associative element is detected using a single comparison between the input key and the boundaries of equivalent non-overlapping ranges. This apparatus may comprise:
a) a first storage area for storing the boundary values of the equivalent non-overlapping data set in an ascending order;
b) a second storage area for storing the associated data set in the in locations that correspond to the locations of closed boundaries of the equivalent non-overlapping data set;
c) a set of comparators for concurrently performing comparisons between each boundary value stored in the first storage area and the input key, to determine whether the input key is larger than the boundary value;
d) circuitry for issuing a TRUE value whenever a comparison result with the input key indicates that the input key is larger than the boundary value, and for issuing a FALSE value if the input key is equal to, or smaller than the boundary value;
e) an encoder for detecting a match whenever there is a transition of the comparison results, from a TRUE value to a FALSE value, and for issuing the index of the last boundary value, for which the comparison result is a TRUE value;
f) a third storage area for storing boundary type information, represented by a bit that indicates whether the boundary value is a closed or opened boundary, the bit is retrieved form the location in the third storage area defined by the index; and
g) circuitry for outputting the associated data that corresponds to the index from the second storage area.
The present invention is also directed to an apparatus, in which each associative element comprises two values, a first value which is the lower boundary of a range, and a second value which is an upper boundary of the range. This apparatus may comprise:
h) an ordered set of storage and detection units for storing the upper and lower boundaries and for detecting a key match represented by issuing a TRUE value, by concurrently performing two comparison operations for the boundaries, a first comparison to determine whether the input key is larger than, or equals to, the range""s lower boundary, and a second comparison to determine whether the input key is smaller than the range""s upper boundary;
i) circuitry for selecting the match with the highest priority, and for issuing the index of the match having the highest priority; and
j) circuitry for outputting the associated data that corresponds to the index.
Each storage and detection unit may generate a validation flag, for enabling/disabling a match detection.
Each value that belongs to a range may be represented in the apparatus by k bits, representing the opened boundary of the range by k+1 bits, such that a xe2x80x9c0xe2x80x9d logic value is assigned to k consecutive bits and a xe2x80x9c1xe2x80x9d logic value is assigned to the remaining bit. Each value that does not belong to a range and is beyond the opened boundary of the range may be represented in the apparatus by k+1 bits, such that a xe2x80x9c0xe2x80x9d logic value is assigned to k consecutive bits and a xe2x80x9c1xe2x80x9d logic value is assigned to the remaining bit. The range may represent Classless Inter Domain Routing (CIDR) addresses.
An input key search may be performed in the apparatus simultaneously in one or more associative elements that may contain the input key, or one or more equivalent non-overlapping ranges that may contain the input key.
The present invention is also directed to an apparatus for storing and outputting associative ranges and their associated data, and for seeking for matching ranges that may contain a searched input key, that comprises:
a) an Entry list storage consisting of an ordered set of Range Words (RW) devices each of which comprises:
a. 1) a first memory cell for storing the lower boundary of an associative range;
a.2) a second memory cell for storing the upper boundary of the associative range;
a.3) an input for inputting the searched input key;
a.4) a validation flag input for indicating that the the lower and upper boundaries are valid;
a.5) an output for indicating a match whenever, the validation flag input provides a valid indication, and the comprises the searched input key;
the RW devices are indexed according to their location, and the ranges that are stored in the RW devices are organized in a priority precedence order.
b) a priority encoder for detecting the match indication from an RW device with the highest priority, the priority encoder comprises:
b.1) inputs for receiving the outputs of the Range Word devices;
b.2) a first output for indicating a match;
b.3) a second output for issuing the index of the matching RW device having the highest priority;
a) a memory for storing the associated data from which the data associated with the highest priority range having a match, is output, the memory comprises:
a.1) a set of memory cells for storing the associated data, each data item of the associated data is stored in a location corresponding to the RW device which stores the range values that the data item is associated with;
a.2) an input of the second output of the priority encoder carrying the index of the match having the highest priority; and
a.3) an output for outputting the data associated with the range having the highest priority match, by utilizing the input as a pointer to the location in which the associated data is stored.
The range value stored in the first memory cell in the apparatus may a closed lower boundary, and the value stored in the second memory cell is an opened upper boundary.
Preferably, the Range Word device comprises:
a) a first comparator having a first input connected to the input of the searched input key, and a second input connected to the first memory cell, and an output for issuing a TRUE indication whenever the value on the first input is smaller than the value on the second input;
b) a second comparator having a first input connected to the input of the searched input key, and a second input connected to the second memory cell, and an output for issuing a TRUE indication whenever the value on the first input is smaller than the value on the second input;
c) an inverter having an input connected to the output of the first comparator, and an output for outputting the inverted comparison result from the first comparator;
d) a first AND gate having an input connected to the output of the inverter, and another input connected to the output of the second comparator, the first AND gate outputs a TRUE indication whenever the searched key is, smaller than the value stored in the second memory cell, and greater than, or equals to, the value stored in the first memory cell; and
e) a second AND gate having an input connected to the output of the first AND gate, and another input connected to the validation flag input, the second AND gate outputs a TRUE indication whenever, a valid indication is obtained from the validation flag input, and a TRUE indication is input into the input from the output of the first AND gate.
The present invention is also directed to an apparatus in which overlapping ranges are converted into one or more equivalent non-overlapping ranges, by combining overlapping ranges by truncating overlapping portions from ranges having lower priority, while maintaining with no change, for each set of overlapping portions, a single portion having the highest priority within the set and by arranging the equivalent non-overlapping ranges of the equivalent set in a descending/ascending order, according to the boundary values of each of the ranges, and each equivalent non-overlapping range has a closed boundary as its lower boundary and an opened boundary as its upper boundary. This apparatus may comprise:
a) an Entry List storage device consisting of an ordered set of memory cells for storing entries, each of which being a value that represents at least one boundary value of a equivalent non-overlapping range and is indexed according to its relative location, the entry comprises a k-bit value, the Entry List storage device comprises:
a.1) an ordered set of boundary entries stored in the order of the equivalent non-overlapping ranges, where an index 1 is assigned to the first boundary value of the first equivalent non-overlapping range that is stored in the first memory cell, and the last boundary value, with index i, is stored in the i""th memory cell;
a.2) zero values stored in all of the remaining memory cells that do not contain boundary values;
b) circuitry for detecting a match between a searched input key and an equivalent non-overlapping range, and for issuing the index of the matching equivalent non-overlapping range, comprising:
b.1) a k-bit key input for inputting the searched input key;
b.2) an input for inputting an Empty flag indication representing a state where the Entry List storage device is empty;
b.3) an ordered set of k-bit inputs, each of which is connected to the output of a corresponding memory cell from the Entry List storage device;
b.4) a set of ordered comparators each of which, except for the first comprator, comprises:
b.4.1) a first input connected to a corresponding k-bit input;
b.4.2) a second input connected to the k-bit key input;
b.4.3) an output for outputting a TRUE indication whenever the value of the first input is smaller than the value of the second input, and a FALSE indication whenever the value of the first input is greater than the value of the second input;
b.4.4) circuitry for producing a logic xe2x80x9c1xe2x80x9d whenever a zero value is obtained on the first input, such that zero values obtained on the first input, are expanded in the comparators into a k+1 bit value having xe2x80x9c1xe2x80x9d at their most significant location, and zeros in all of the remaining locations;
b.5) a first comparator that comprises:
b.5.1) a first input connected to the first k-bit input;
b.5.2) a second input connected to the k-bit key input;
b.5.3) an output for outputting a TRUE indication whenever the value of the first input is smaller than the value of the second input, and a FALSE indication whenever the value of the first input is greater than the value of the second input;
b.6) a Range Encoder for producing the index of a matching range whenever the Entry List storage device is not empty, by detecting the transition point of the outputs of the set of ordered comparators from a series of consecutive TRUE indications to a FALSE indication, and for producing an indication whenever the searched input key is larger than any entry in the Entry List storage device;
c) a Boundary Type storage device for storing and outputting a match or mismatch indication whenever the index of a matching range value that is received, corresponds to a closed boundary value, the Boundary Type storage device comprises:
c.1) an ordered set of storage device containing boundary type bits each of which corresponds to a memory cell in the Entry List storage device, and is utilized for storing xe2x80x9c1xe2x80x9d whenever a closed boundary is stored in the corresponding memory cell, and for storing xe2x80x9c0xe2x80x9d whenever an opened boundary is stored in the memory cell;
c.2) an input for inputting the index;
c.3) an output for outputting the boundary type bits, that is utilized for indicating a match or a mismatch;
c.4) circuitry for outputting the boundary type bits on the output, utilizing the index value received on the input to select the boundary type bit from the ordered set of storage device;
d) associated data storage device for storing and outputting the data associated with each range of the equivalent non-overlapping set of ranges, the associated data storage device comprises:
d.1) an ordered set of memory cells for storing associated data in locations that correspond to the locations of the closed boundary values having association with the associated data;
d.2) an input for inputting the index;
d.3) an output for outputting associated data stored in the ordered set of memory cells;
d.4) circuitry for outputting the associated data on the output, utilizing the index value received on the input to retrieve the associated data from the ordered set of memory cells; and
e) circuitry for disabling/enabling the output from the Boundary Type storage device by utilizing the indication of a searched input key that is larger than any entry in the Entry List storage device, to disable/enable the output from the Boundary Type storage device.
The Range Encoder may comprise:
a) a set of ordered inputs for receiving the outputs of the set of ordered comparators;
b) an input for receiving an Entry List Empty indication, whenever the Entry List storage device does not comprise associative data;
c) a first output for outputting the index of the matching range value;
d) a second output for outputting an indication whenever the searched input key is larger than any range value stored in the Entry List storage device; and
e) an encoder for outputting the index of the matching range.